Path computation for tunnels of a computer network, e.g., label switched paths (LSPs), is generally performed in a distributed manner, where each head-end node of the tunnels computes paths for its tunnels independently from head-end nodes of other tunnels. For example, tunnels in many Multi-Protocol Label Switching (MPLS) Traffic Engineering (TE) networks (e.g., MPLS TE-LSPs) are computed using a distributed constrained shortest path first (CSPF) algorithm. As those skilled in the art will understand, distributed CSPF offers high flexibility/scalability, and is well-equipped to handle frequent topology changes, dynamic traffic demands, and resource availability changes.
One problem associated with distributed path computation is that while it may be highly flexible/scalable, it may be inefficient for optimizing tunnel placement within the network, particularly due to the lack of path computation coordination among the head-end nodes. By not coordinating the path computation of tunnels (i.e., beyond being aware of what tunnels currently exist in the network), available resources of the network (e.g., bandwidth) may be allocated inefficiently and may become fragmented. Bandwidth fragmentation, in turn, may result in an inability to place larger tunnels (i.e., those reserving larger bandwidth) because of the placement of the smaller tunnels previously established. For instance, if many smaller tunnels are reserved throughout the network, those smaller tunnels may “fragment” the bandwidth of the network, to the extent that even if a large amount of bandwidth is available from a source to a destination, that bandwidth may be fragmented into smaller amounts along multiple paths such that no one path exists upon which a large tunnel may be placed. Also, where a path does exist for the larger tunnels, that path may be at a larger (e.g., substantially larger) cost (e.g., cost, length, etc.) than had the larger tunnels been placed before the smaller tunnels.
Due to the distributed nature of path computation for tunnels (e.g., distributed CSPF), it has generally not been possible to coordinate the establishment of large and small tunnels in a computer network such that substantially all tunnels can be placed (provided there is sufficient bandwidth for all tunnels as a whole), and at a lower network-average cost. Previous attempts to place larger tunnels involved using priority levels to denote larger tunnels (higher priority) and smaller tunnels (lower priority). These attempts, however, are complex in design, and because there are commonly only a limited number of priorities (e.g., eight), the use of priority is limited in scalability for wide ranges of tunnel sizes. Furthermore, such a scheme generally cannot be used for tunnels that have the same priority.